import org.w3c.dom.Node;

import java.sql.SQLOutput;
import java.util.Scanner;

public class Tree {
    public static void main(String[] args) {
        //根就是指当前节点
         TreeNode root=new TreeNode(1,"宋江");
        TreeNode node2=new TreeNode(2,"吴用");
        TreeNode node3=new TreeNode(3,"卢俊");
        TreeNode node4=new TreeNode(4,"林冲");
        BinaryTree binaryTree=new BinaryTree(root);
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        Scanner sc=new Scanner(System.in);
       while(true){
           System.out.println("\n"+"-----------------------------------------------------------------------------");
           System.out.println("1 遍历二叉树、2 查找二叉树的结点、3 修改二叉树的结点、4 删除二叉树的结点、5 退出");
           System.out.println("请选择要进行的操作：");
           int choice=sc.nextInt();
           if(choice==1){
               System.out.println("请输入遍历的方式：（前序遍历 中序遍历 后序遍历）");
           }else if(choice==2){
               System.out.println("请输入查找的方式：（前序查找 中序查找 后序查找）");
           } else if(choice==3){
               System.out.println("请输入修改的方式：（前序修改 中序修改 后序修改）");
           } else if(choice==4){
               System.out.println("请输入查找的方式：（前序删除 中序删除 后序删除）");
           }else if(choice==5){
               Menu(binaryTree,"退出");
           }else{
               System.out.println("没有这个选项");
               continue;
           }
           String way=sc.next();
           Menu(binaryTree,way);
       }

    }
    public static void Menu(BinaryTree binaryTree,String way){
        switch (way){
            case "前序遍历"->binaryTree.PrePrint();
            case "中序遍历"->binaryTree.MidPre();
            case "后序遍历"->binaryTree.BehPrint();
            case "前序查找"-> binaryTree.preSearch();
            case "中序查找"->binaryTree.MidSearch();
            case "后序查找"->binaryTree.PostSearch();
            case "前序修改"-> binaryTree.PreModify();
            case "中序修改"->System.out.println("中序修改");
            case "后序修改"->System.out.println("后序修改");
            case "前序删除"-> binaryTree.Delete();
            case "中序删除"->System.out.println("中序删除");
            case "后序删除"->System.out.println("后序删除");
            default-> System.exit(0);

        }
    }
}

//创建二叉树
class BinaryTree{
    //根结点
    private TreeNode root;

    //构造器
    public BinaryTree(TreeNode root){
        this.root=root;

    }
    Scanner sc=new Scanner(System.in);

    //删除结点
    public void Delete(){
        System.out.println("请输入要删除的结点的编号：");
        int num=sc.nextInt();
        if(root==null){
            System.out.println("该树为空");
        }else{
            root.DelNode(num);
        }
    }

    //前序修改
    public void PreModify(){
        System.out.println("请输入要修改的结点");
        int num=sc.nextInt();
        if(root!=null){
            if(root.PreModifyNode(num)){
                System.out.println("添加成功！");
            }else{
                System.out.println("不存在该编号！");
            }
        }
    }

    //前序查找
    public void preSearch(){
        System.out.println("请输入要查找的结点");
        int num=sc.nextInt();
        if(root!=null){
            if(root.PreSearchNode(num)==null){
                System.out.println("不存在该编号！");
            }
        }
    }
    //中序查找
    public void MidSearch(){
        System.out.println("请输入要查找的结点");
        int num=sc.nextInt();
        if(root!=null){
            if(root.MidOrderSearchNode(num)==null){
                System.out.println("不存在该编号！");
            }
        }
    }
    //后序查找
    public void PostSearch(){
        System.out.println("请输入要查找的结点");
        int num=sc.nextInt();
        if(root!=null){
            if(root.PostSearchNode(num)==null){
                System.out.println("不存在该编号！");
            }
        }
    }

    //前序遍历
    public void PrePrint(){
        if(root!=null){
            root.Pre();
        }else{
            System.out.println("此树不存在！");
        }
    }
    //中序遍历
    public void MidPre(){
        if(root!=null){
            root.mid();
        }else{
            System.out.println("此树不存在！");
        }
    }
    //后序遍历
    public void BehPrint(){
        if(root!=null){
            root.behind();
        }else{
            System.out.println("此树不存在！");
        }
    }
}




//创建结点
class TreeNode{
    public int num;//编号
    public String name;//姓名
    public TreeNode left;//左子树
    public TreeNode right;//右子树

    //构造器
    public TreeNode(int num,String name){
        this.num=num;
        this.name=name;

    }
    //get、set方法


    public void setNum(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public TreeNode getRight() {
        return right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
    Scanner sc=new Scanner(System.in);

    //删除
    public void DelNode(int num){
        //目前就只实现：删除的是叶子结点就直接删除，若删除的是非叶子结点就把这棵树删除
        if(this.left!=null && this.left.num==num){
            //删除左子树
            this.left=null;
        }
        if(this.right!=null && this.right.num==num){
            //删除右子树
            this.right=null;
        }
        if(this.left!=null){
            this.left.DelNode(num);
        }
        if(this.right!=null){
            this.right.DelNode(num);
        }

    }

    //前序修改
    public boolean PreModifyNode(int num) {
        if (this.getNum() == num) {
            System.out.println("请输入修改后的编号：");
            this.setNum(sc.nextInt());
            System.out.println("请输入修改后的名字：");
            this.setName(sc.next());
            return true;
        }//根

        boolean temp = false;
        if (this.getLeft() != null) {
            //左递归查找--找到了会返回调用处--
            temp = this.left.PreModifyNode(num);
        }
        if (temp) {//接收的是递归的返回值
            return true;
        }
        if (this.right != null) {
            temp = this.right.PreModifyNode(num);
        }

        return temp;

    }

    //前序查找结点--找到就返回，找不到就返回null
    public TreeNode PreSearchNode(int num){
        if(this.getNum()==num){
            System.out.println(this.toString());
            return this;
        }//根

        TreeNode tempNode=null;
        if(this.getLeft()!=null){
            //左递归查找--找到了会返回调用处--
            tempNode=this.left.PreSearchNode(num);
        }
        if(tempNode!=null){//接收的是递归的返回值
            return tempNode;
        }
        if(this.right!=null){
           tempNode=this.right.PreSearchNode(num);
        }

        return tempNode;

    }
    //中序查找
    public TreeNode MidOrderSearchNode(int num) {
        TreeNode tempNode=null;
        if(this.left!=null){
            tempNode=this.left.MidOrderSearchNode(num);
        }
        if(tempNode!=null){
            return tempNode;
        }
        if(this.getNum()==num){
            System.out.println(this.toString());
            return this;
        }
        if(this.getRight()!=null){
            tempNode=this.right.MidOrderSearchNode(num);
        }

        return tempNode;

    }
    //后续查找
    public TreeNode PostSearchNode(int num) {
        TreeNode tempNode=null;
        if(this.left!=null){
            tempNode=this.left.PostSearchNode(num);
        }
        if(tempNode!=null){
            return tempNode;
        }
        if(this.getRight()!=null){
            tempNode=this.right.PostSearchNode(num);
        }
        if(this.getNum()==num){
            System.out.println(this.toString());
            return this;
        }
        return tempNode;
    }
    //前序遍历
    public void Pre(){
        //根左右---根就是指当前节点
        System.out.println(this.toString());//根

        if(this.left!=null){
            this.left.Pre();
        }
        if(this.right!=null){
            this.right.Pre();
        }

    }
    //中序遍历
    public void mid(){
        //左根右
        if(this.left!=null){
            this.left.mid();
        }
        System.out.println(this.toString());//根
        if(this.right!=null){
            this.right.mid();
        }


    }
    //后序遍历
    public void behind(){
        //左右根
        if(this.left!=null){
            this.left.behind();
        }
        if(this.right!=null){
            this.right.behind();
        }
        System.out.println(this);//根

    }





}